package lab6;

import java.util.ArrayList;
import java.util.LinkedList;

public class FordFulkerson {
	private int[] parent;
	private int nbrOfNodes;
	private LinkedList<Integer> queue;
	private boolean[] visited;
	
	public FordFulkerson(int nbrOfNodes) {
		this.nbrOfNodes = nbrOfNodes;
		parent  = new int[nbrOfNodes + 1];
		this.queue = new LinkedList<Integer>();
		visited = new boolean[nbrOfNodes + 1];
	}
	
	public int maxFlow(int graph[][], int source, int sink) {
		int u, v;
		int pathFlow;
		int maxFlow = 0;
		int[][] residualGraph = new int[nbrOfNodes + 1][nbrOfNodes + 1];
		ArrayList<String> minimumCut = new ArrayList<String>();
		
		for(int sourceNode = 0; sourceNode < nbrOfNodes; sourceNode++) {
			for(int sinkNode = 0; sinkNode < nbrOfNodes; sinkNode++){
				residualGraph[sourceNode][sinkNode] = graph[sourceNode][sinkNode];
			}
		}
		
		while(bfs(source, sink, residualGraph)) {
			pathFlow = Integer.MAX_VALUE;
			for(v = sink; v != source; v = parent[v]) {
				u = parent[v];
				if(pathFlow > residualGraph[u][v]) {
					pathFlow = residualGraph[u][v];

				}
			}
			
			for(v = sink; v != source; v = parent[v]) {
				u = parent[v];
				residualGraph[u][v] -= pathFlow;
				residualGraph[v][u] += pathFlow;
			}
			
			maxFlow += pathFlow;
		}
		
		System.out.println("\nMinimum cut:");
		for(int i = 0; i < nbrOfNodes; i++) {
			for(int j = i; j < nbrOfNodes; j++) {
				if(visited[i] != visited[j] && graph[i][j] != 0) {
					System.out.println(i + " " + j + " " + graph[i][j]);
				}
			}
		}
		
		return maxFlow;
	}
	
	public boolean bfs(int source, int sink, int graph[][]) {
		int destination, element;
		boolean pathFound = false;
		
		for(int node = 1; node <= nbrOfNodes; node++) {
			parent[node] = -1;
			visited[node] = false;
		}
		
		queue.add(source);
		parent[source] = -1;
		visited[source] = true;
		
		while(!queue.isEmpty()) {
			destination = 1;
			element = queue.remove();
			
			while(destination < nbrOfNodes) {
				if(graph[element][destination] > 0 && !visited[destination]) {
					queue.add(destination);
					parent[destination] = element;
					visited[destination] = true;
				}
				destination++;
			}
		}
		
		if(visited[sink])
			pathFound = true;
		
		return pathFound;
	}
}
